package com.algorithm.prim;

public class MinTree {
    Graph graph;

    public MinTree(Graph graph){
        this.graph = graph;
    }

    public void showGraph(){
        for(int[] linke:graph.weight){
            for(int d:linke){
                System.out.format("%-6d",d);
            }
            System.out.println();
        }
    }

    /**
     * 普利姆算法生成最小生成树:
     * 对无向图中的已被访问的结点和未被访问的结点之间的边进行遍历，每次遍历过程中记录两个顶点，以及顶点之间的权值
     * 最终比较得到权值最小的边以及相邻的顶点
     * @param graph 给定的图
     * @param v 从第v个顶点开始
     */
    public void prim(Graph graph,int v){
        //记录图中结点是否被访问过
        boolean[] visited = new boolean[graph.verxs];
        //记录遍历时的顶点的下标和边的权值
        int h1 = -1;
        int h2 = -1;
        int minWeight = 1000;
        //将初始顶点标记为已访问
        visited[v] = true;

        //根据普利姆算法特性n个结点最小生成树的边为n-1个，所以需要进行n-1次循环找到每条边
        for(int k = 0;k < graph.verxs-1;k++){
            //遍历已访问的结点
            for(int i = 0;i<graph.verxs;i++){
                //遍历未被访问的结点
                for(int j = 0;j<graph.verxs;j++){
                    //如果一个已被访问的结点和一个未被访问的结点之间的权值小于minWeight则记录
                    //不连通时的权值为1000故不满足条件
                    if(visited[i] == true && visited[j] == false && graph.weight[i][j] < minWeight){
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            System.out.println("当前权值最小的边为<"+graph.data[h1]+","+graph.data[h2]+">,权值为:"+minWeight);
            visited[h2] = true;
            //重置minWeight
            minWeight = 1000;
        }
    }
}

